Consider the iterative implementation of binary search shown below:

import math

def iterative_binary_search(arr, target):

    start = 0
    stop = len(arr)

    while (stop - start) > 0:
        print(arr[start])
        middle = math.floor((start + stop) / 2)
        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            stop = middle
        else:
            start = middle + 1

    return None

Which of the following loop invariants is true, assuming that arr is sorted and non-empty, and target is not in the array? Select all that apply.

Consider iterative_binary_search below and note the print statement in the while-loop:

import math

def iterative_binary_search(arr, target):

    start = 0
    stop = len(arr)

    while (stop - start) > 0:
        print(arr[start])
        middle = math.floor((start + stop) / 2)
        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            stop = middle
        else:
            start = middle + 1

    return None

Suppose iterative_binary_search is run on the array:

[-202, -201, -200, -50, -20, -10, -4, -3, 0, 1, 3, 5, 6, 7, 9, 10, 12, 15, 22]

with target 11.

What will be the last value of arr[start] printed?

Recall the partition operation from quickselect. Which of the following arrays could have been partitioned at least once? Select all that apply.

Consider this code which partitions a list in a special way:

def is_even(i):
    """Returns True if i is even, False otherwise."""
    return i % 2 == 0

def mystery_partition(numbers):
    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    barrier_ix = 0
    for i in range(len(numbers)):
        if is_even(numbers[i]):
            swap(i, barrier_ix)
            if numbers[barrier_ix] > numbers[0]:
                swap(0, barrier_ix)
            barrier_ix += 1


lst = [1, 5, 3, 7, 2, 4, 8, 5, 9, 6, 100]
mystery_partition(lst)
print(lst)

Which of the following loop invariants are true for this code? Select all that apply.

Note: any statement about an empty set or list is considered to be automatically true.